home *** CD-ROM | disk | FTP | other *** search
/ CD Ware Multimedia 1995 May / cd Ware (Juegos) Epimundo.iso / DOS / C / AVLTREE.ZIP / AVLTREE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1987-02-11  |  8.2 KB  |  329 lines
  1. /* avltree.c - AVL tree processing functions */
  2.  
  3. #include "avltree.h"
  4. #include <malloc.h>
  5. #include <stdio.h>
  6.  
  7. #define     die(x)  {fprintf(stderr,"%s (%d): fatal error - %s\n",__FILE__,__LINE__,(x));exit(-1);}
  8.  
  9. /* find_in_tree - find key in tree */
  10.  
  11. avl_tree find_in_tree(key, t)
  12. char *key; avl_tree t;      {
  13.  
  14.     avl_tree tp;        /* pointer to current tree node */
  15.     boolean found;      /* has key been found?          */
  16.     int test;           /* value of comparision         */
  17.     tp = t;
  18.     found = FALSE;
  19.     while (tp != NULL && !found)    {
  20.         test = strcmp(key,tp->avl_key);
  21.         if (test == 0)
  22.             found = TRUE;
  23.         else if (test < 0)
  24.             tp = tp->avl_left;
  25.         else if (test > 0)
  26.             tp = tp->avl_right;
  27.         else
  28.             die("Unknown int from strcmp in find_in_tree");
  29.         }
  30.     return(tp);
  31.     }
  32.  
  33. /* init_tree (local) - set up one node AVL tree */
  34.  
  35. static avl_tree init_tree(key, data)
  36. char *key, *data;           {
  37.  
  38.     avl_tree new_tree;
  39.  
  40.     new_tree = (avl_tree) calloc(1,sizeof(struct avl_node));
  41.     new_tree->avl_left = new_tree->avl_right = NULL;
  42.     new_tree->_avl_bf = 0;
  43.     new_tree->avl_key = key;
  44.     new_tree->avl_data = data;
  45.     return(new_tree);
  46.     }
  47.  
  48. /* locate_ins_point (local) - find point to add node to AVL tree */
  49.  
  50. static void locate_ins_point(key, data, t, pivot, pivot_parent, previous)
  51. char *key, *data; avl_tree t, *pivot, *pivot_parent, *previous;     {
  52.  
  53.     avl_tree current;
  54.     boolean found;
  55.     int test;
  56.  
  57.     *pivot_parent = *previous = NULL;
  58.     *pivot = current = t;
  59.     found = FALSE;
  60.  
  61.         /* search t for insertion point */
  62.  
  63.     while (current != NULL && !found)   {
  64.  
  65.             /* check for pivot */
  66.  
  67.         if (current->_avl_bf != 0)  {
  68.             *pivot = current;
  69.             *pivot_parent = *previous;
  70.             }
  71.  
  72.             /* see what direction to go */
  73.  
  74.         test = strcmp(key, current->avl_key);
  75.  
  76.             /* we shouldn't get here */
  77.  
  78.         if (test == 0)  {
  79.             found = TRUE;
  80.             current->avl_data = data;
  81.             }
  82.  
  83.             /* left branch? */
  84.  
  85.         else if (test < 0)  {
  86.             *previous = current;
  87.             current = current->avl_left;
  88.             }
  89.  
  90.             /* right branch? */
  91.  
  92.         else if (test > 0)  {
  93.             *previous = current;
  94.             current = current->avl_right;
  95.             }
  96.  
  97.         else
  98.             die("Unknown int from strcmp in locate_ins_point");
  99.         }
  100.     }
  101.  
  102. /*
  103.  * adj_bf (local) - adjust balance factors in AVL tree
  104.  *                  from pivot down.  Returns delta_bf.
  105.  */
  106.  
  107. static int adj_bf(pivot, heavy_side, new_node)
  108. avl_tree pivot, *heavy_side, new_node;          {
  109.  
  110.     avl_tree current;
  111.     int test, delta_bf;
  112.  
  113.     test = strcmp(new_node->avl_key, pivot->avl_key);
  114.     if (test > 0)   {
  115.         *heavy_side = current = pivot->avl_right;
  116.         delta_bf = -1;
  117.         }
  118.     else    {
  119.         *heavy_side = current = pivot->avl_left;
  120.         delta_bf = 1;
  121.         }
  122.  
  123.     while (current != new_node)     {
  124.  
  125.         test = strcmp(new_node->avl_key, current->avl_key);
  126.  
  127.             /* height of right increases by 1 */
  128.         if (test > 0)   {
  129.             current->_avl_bf = -1;
  130.             current = current->avl_right;
  131.             }
  132.  
  133.             /* height of left increases by 1 */
  134.         else    {
  135.             current->_avl_bf = 1;
  136.             current = current->avl_left;
  137.             }
  138.         }
  139.     pivot->_avl_bf += delta_bf;
  140.     return(delta_bf);
  141.     }
  142.  
  143. /* ll rotate (local) - perform LL rotation and return new root */
  144.  
  145. static avl_tree ll_rotate(pivot)
  146. avl_tree pivot;                     {
  147.  
  148.     avl_tree heavy_side;
  149.  
  150.     heavy_side = pivot->avl_left;
  151.     pivot->avl_left = heavy_side->avl_right;
  152.     heavy_side->avl_right = pivot;
  153.     pivot->_avl_bf = 0;
  154.     return(heavy_side);
  155.     }
  156.  
  157. /* lr rotate (local) - perform LR rotation and return new root */
  158.  
  159. static avl_tree lr_rotate(pivot)
  160. avl_tree pivot;                     {
  161.  
  162.     avl_tree new_root, heavy_side;
  163.  
  164.     heavy_side = pivot->avl_left;
  165.     new_root = heavy_side->avl_right;
  166.     heavy_side->avl_right = new_root->avl_left;
  167.     pivot->avl_left = new_root->avl_right;
  168.     new_root->avl_left = heavy_side;
  169.     new_root->avl_right = pivot;
  170.  
  171.     switch(new_root->_avl_bf)   {
  172.  
  173.         case 1:    /* LR(b) */
  174.             pivot->_avl_bf = -1;
  175.             heavy_side->_avl_bf = 0;
  176.             break;
  177.  
  178.         case -1:    /* LR(c) */
  179.             heavy_side->_avl_bf = 1;
  180.             pivot->_avl_bf = 0;
  181.             break;
  182.  
  183.         case 0:     /* LR(a) */
  184.             pivot->_avl_bf = 0;
  185.             heavy_side->_avl_bf = 0;
  186.             break;
  187.  
  188.         default:
  189.             die("bad balance factor in LR rotate");
  190.         }
  191.     new_root->_avl_bf = 0;
  192.     return(new_root);
  193.     }
  194.  
  195. /* rr rotate (local) - perform RR rotation and return new root */
  196.  
  197. static avl_tree rr_rotate(pivot)
  198. avl_tree pivot;                     {
  199.  
  200.     avl_tree heavy_side;
  201.  
  202.     heavy_side = pivot->avl_right;
  203.     pivot->avl_right = heavy_side->avl_left;
  204.     heavy_side->avl_left = pivot;
  205.     pivot->_avl_bf = 0;
  206.     heavy_side->_avl_bf = 0;
  207.     return(heavy_side);
  208.     }
  209.  
  210. /* rl rotate (local) - perform the RL rotation and return the new root */
  211.  
  212. static avl_tree rl_rotate(pivot)
  213. avl_tree pivot;                     {
  214.  
  215.     avl_tree new_root, heavy_side;
  216.  
  217.     heavy_side = pivot->avl_right;
  218.     new_root = heavy_side->avl_left;
  219.     heavy_side->avl_left = new_root->avl_right;
  220.     pivot->avl_right = new_root->avl_left;
  221.     new_root->avl_right = heavy_side;
  222.     new_root->avl_left = pivot;
  223.  
  224.     switch(new_root->_avl_bf)   {
  225.  
  226.         case -1:    /* RL(b) */
  227.             pivot->_avl_bf = 1;
  228.             heavy_side->_avl_bf = 0;
  229.             break;
  230.  
  231.         case 1:    /* RL(c) */
  232.             heavy_side->_avl_bf = -1;
  233.             pivot->_avl_bf = 0;
  234.             break;
  235.  
  236.         case 0:     /* RL(a) */
  237.             pivot->_avl_bf = 0;
  238.             heavy_side->_avl_bf = 0;
  239.             break;
  240.  
  241.         default:
  242.             die("bad balance factor in RL rotate");
  243.         }
  244.     new_root->_avl_bf = 0;
  245.     return(new_root);
  246.     }
  247.  
  248. /* AVL insert - add node to AVL tree.  Pointer to tree node is returned */
  249.  
  250. avl_tree avl_insert(key, data, t)
  251. char *key, *data; avl_tree *t;       {
  252.  
  253.     avl_tree pivot, heavy_side, new_root, pivot_parent, previous, new_node;
  254.     boolean found;
  255.     int delta_bf;
  256.  
  257.         /* special case - empty tree */
  258.  
  259.     if (*t == NULL) {
  260.         *t = init_tree(key, data);
  261.         return(*t);
  262.         }
  263.  
  264.         /* find insertion point and create node */
  265.  
  266.     locate_ins_point(key, data, *t, &pivot, &pivot_parent, &previous);
  267.     new_node = init_tree(key, data);
  268.  
  269.         /* insert node */
  270.  
  271.     if (strcmp(key, previous->avl_key) < 0)
  272.         previous->avl_left = new_node;
  273.     else
  274.         previous->avl_right = new_node;
  275.  
  276.     delta_bf = adj_bf(pivot, &heavy_side, new_node);
  277.  
  278.     if (pivot->_avl_bf >= 2 || pivot->_avl_bf <= -2)    {
  279.  
  280.             /* left imbalance */
  281.  
  282.         if (delta_bf == 1)
  283.             if (heavy_side->_avl_bf == 1)
  284.                 new_root = ll_rotate(pivot);
  285.             else
  286.                 new_root = lr_rotate(pivot);
  287.  
  288.             /* right imbalance */
  289.  
  290.         else
  291.             if (heavy_side->_avl_bf == -1)
  292.                 new_root = rr_rotate(pivot);
  293.             else
  294.                 new_root = rl_rotate(pivot);
  295.  
  296.             /* relink balanced subtree */
  297.  
  298.         if (pivot_parent == NULL)
  299.             *t = new_root;
  300.         else if (pivot == pivot_parent->avl_left)
  301.             pivot_parent->avl_left = new_root;
  302.         else if (pivot == pivot_parent->avl_right)
  303.             pivot_parent->avl_right = new_root;
  304.         else
  305.             die("lost subtree in AVL insert");
  306.         }
  307.     return(new_node);
  308.     }
  309.  
  310. /* sideview - output tree recursively */
  311.  
  312. void sideview(depth, t)
  313. int depth; avl_tree t;  {
  314.  
  315.     register int i;
  316.  
  317.     if (t != NULL)  {
  318.         sideview(depth + 1, t->avl_right);
  319.         for (i = 0; i < 2 * depth; i++) {
  320.             putchar(' ');
  321.             }
  322.         printf("%d BF=%d %s:%s\n", depth, t->_avl_bf,t->avl_key, t->avl_data);
  323.         sideview(depth + 1, t->avl_left);
  324.         }
  325.     }
  326.  
  327.  
  328.  
  329.